1. Field of the Invention
The invention relates generally to the field of digital data processing systems, and more specifically to systems for processing bits representing digitized images to produce perceptually similar images with fewer bits than the original.
2. Description of the Prior Art
A problem in digital image processing is the vast amount of data, expressed in binary digits or "bits", which are used to describe a digital image. Digital images are defined in terms of picture elements, or "pixels", with each pixel being the smallest unit of an image which the data processing system can process and display. Depending on the size of the image and the resolution, a low-resolution two-dimensional rectangular image may have as few as several tens or a hundred pixels on a side, and some high-resolution images have as many as a thousand or more pixels on a side.
Depending on a number of factors, each pixel may also have as many as eight, sixteen or more bits of data in a "continuous-tone" image. In a monochrome image, the data associated with each pixel typically identifies a "luminance" level, which is a measure of the brightness of the pixel. In a color image, the data may also identify various color components and their relative brightness in the pixel. For example, in a some monochrome displays, each pixel may be black (a low luminance level) or white (a high luminance level), or it may have these plus a number of intermediate, or "gray", brightness levels. The luminance of a pixel is typically expressed as a binary encoded value, such that if, for example, eight bits are used to encode each pixel, the luminance of the pixel may have up to two hundred fifty six (that is, 2.sup.8) different gray levels, including the black and white extremes. If the image has several colors, bits must also be used to identify the color, and, perhaps, the relative brightness level of each color in the pixel.
While an image may be defined in terms of its "continuous-tone" image values, in which each pixel is defined by eight or more bits of data, display devices such as video display terminals and printers normally can only accommodate one or at most a few bits of data for each pixel to define the luminance of the displayed pixel. Images in which a pixel's luminance is defined by one bit per pixel are termed "halftone" images, while, more generally, images in which the pixel luminance is defined by one or only a few bits of data (but fewer bits than are required for the continuous tone image) are termed "dithered" images. The continuous tone image data is processed to generate the output luminance values for the pixels ("pixel values") to define the halftone or dithered image for the display device.
Several techniques have been developed to generate pixel values so that the image as rendered by the display device is perceptually similar to the actual image. One popular technique for producing halftone image data makes use of an "error diffusion" algorithm described in R.W. Floyd, et al., "An Adaptive Algorithm for Spatial Greyscale", Proceeding of the S.I.D., Vol. 17/2, Second Quarter, 1976. In that technique, the continuous-tone image is processed pixel by pixel to produce halftone output values for each pixel. The pixels are processed line by line from the top of the image to the bottom of the image. The processing takes place in a raster pattern, that is, from left to right in each line. In processing each pixel, a correction value, which is related to previous processing of pixels in the image, is added to the continuous tone value to produce a modified pixel value. Based on the modified pixel value, an output pixel value is then assigned one of two halftone values to indicate to the display device whether it should display the pixel as white or black in the halftone image.
After the processed pixel is assigned the halftone output value, an error value is determined between the output pixel value and the modified pixel value. The error value represents the difference between the selected halftone value assigned to the pixel and the actual modified pixel value. The error values are used in calculating the correction value for subsequently processed pixels. The correction value which is used in calculating the modified pixel value of each pixel is related to sum of error values of nearby previously processed pixels, which have been multiplied by various predetermined weighting values. The weighting values have been empirically selected to produce halftone images which are perceptually similar to the continuous-tone images.
The point of the error diffusion technique is that the error values, which, generally speaking, relate to the difference between the white and black luminances in the output halftone image and the gray pixel levels in the original continuous tone image, are diffused as processing proceeds to the right and downwardly in the image. Thus, while the halftone pixel value of any given pixel may be considerably different from the continuous-tone pixel level, over a group of pixels the error tends to even out so that the halftone image is perceptually similar to the continuous tone image.
While the error diffusion technique produces fairly good images, from a perceptual standpoint, it does have several problems. The primary problem is that it tends to produce undesirable artifacts, such as directional structures, in the halftoned image which are not present in the original continuous tone image. These artifacts are usually present in portions of an image which have large areas of constant or slowly-varying luminance. In addition, the technique tends to sharpen abrupt edges in a unidirectional manner.